The invention relates to analyzing an image of an arrangement of discrete objects.
The usefulness of a product expected to include items or attributes in a predetermined arrangement is diminished by a defect relating to the arrangement. If the product is meant to be a component in another product, this defect may ruin the other product.
For this reason, products incorporating such items or attributes in such predetermined arrangements may be inspected for compliance with some standard. Examples of products appropriate for inspection include ball grid array devices, micro-ball grid arrays, flip chips, and chip-scale packages (together called "BGAs"). BGAs share a common feature in that the contacts on the device are metallic balls that are mounted on one side of the device for forming electrical connections between the package's integrated circuit and a printed circuit board.
To work properly, the balls of BGAs should be properly located to connect to the pads on the circuit board. The balls also should be properly formed (i.e., should have a spherical shape and neither too much nor too little solder, to allow an acceptable electrical connection). The balls also should not be connected by extraneous solder or other material in the spaces between the balls. If these conditions are not met, the BGA may fail to make proper electrical connections or durable physical bonds.
Unlike traditional leaded devices that have contacts exposed on perimeters where some types of defects (e.g., solder bridges or missing solder) can be detected even after soldering, BGAs are harder to inspect after mounting on a circuit board. BGAs therefore are inspected before mounting, either in fully-assembled form or by inspection of ball arrays that are about to be attached to the packages of integrated circuits.
Inspections are done on other types of products, e.g., pill blister packs and candy sampler boxes.
Typically, such inspections are conducted according to a "brute force" correspondence-finding method in which the amount of computational resources required is at least roughly proportional to the factorial of the number of objects of interest that are associated with each device to be inspected (e.g., where 3,628,800 processing cycles are required for a device having 10 objects of interest, more than 2.4.times.10.sup.18 such cycles are required for an object having 20 objects of interest). Where the number of objects of interest is large, a lack of sufficient computational resources may impede the quick identification of missing and extra objects in the actual arrangement. Also, in a real-time inspection application, the brute force method may leave little time for analyzing the quality of other objects found in the actual arrangement.